/*
* 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
*   如果有两个中间结点，则返回第二个中间结点
*
*
*/

#include "common.h"


/*
定义一个快指针，一个慢指针。快指针一次走两步，慢指针一次走一步。当快指针走到结尾时，慢指针指向的就是中间节点。
    两个中间结点的时候，返回第二个中间结点：当前快指针和当前快指针的下一个结点都非空
    在两个中间结点的时候，返回第一个中间结点：当前快指针的下一个结点和当前快指针的下下一个结点都非空
*/
struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* first = head;
    struct ListNode* second = head;
    while(first && first->next){
        second = second->next;
        first = first->next->next;
    }
    return second;
}